package genetic;


import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
import java.util.Vector;

public abstract class Phenotype {

	public abstract double fitness(Genotype g);
	public abstract Genotype createRandomInstance();
	public abstract Genotype[] crossover(Genotype g1, Genotype g2);
	public abstract Genotype mutate(Genotype g, double Pm);
	public abstract List<Genotype> getMatingPool(List<Genotype> population, int populationSize);
	public abstract void updateFitness(List<Genotype> population);
	public abstract List<Genotype> getInitialPopulation(int populationSize);

	public List<Genotype> getInitialRandomPopulation(int size){
		List<Genotype> population = new LinkedList<Genotype>();
		for (int i = 0; i < size; i++) {
			population.add(createRandomInstance());
		}
		return population;
	}


	// permutation operators
	protected int[] getRandomIntString(int size, int offset){
		int[] ans = new int[size];
		Vector<Integer> tmp = new Vector<Integer>();
		for (int i=1; i<size+1; i++){
			tmp.add(i+offset);
		}
		int index = 0;
		while (!tmp.isEmpty()){
			int random = (int)(Math.random()*(double)tmp.size());
			ans[index] = tmp.remove(random);
			index++;
		}
		return ans;
	}

	//crossover
	protected int[][] order1crossover(int[] p1, int[] p2){
		int[][] kids = new int[2][p1.length];
		int[] rand = getRandomPair(p1.length);

		Set<Integer> tmp1 = new TreeSet<Integer>();
		Set<Integer> tmp2 = new TreeSet<Integer>();
		for (int i=rand[0]; i<=rand[1]; i++){
			kids[0][i] = p1[i];
			tmp1.add(p1[i]);
			kids[1][i] = p2[i];
			tmp2.add(p2[i]);
		}
		int index = (rand[1]+1) % p1.length;
		int tmp = index;
		while(index!=rand[0]){
			if (!tmp1.contains(p2[tmp])){
				kids[0][index] = p2[tmp];
				index = (index+1) % p1.length;
			}
			tmp = (tmp+1) % p1.length;
		}
		index = (rand[1]+1) % p1.length;
		tmp = index;
		while(index!=rand[0]){
			if (!tmp2.contains(p1[tmp])){
				kids[1][index] = p1[tmp];
				index = (index+1) % p1.length;
			}
			tmp = (tmp+1) % p1.length;
		}
		return kids;
	}

	protected int[][] pmxCrossover(int[] p1, int[] p2){
		int[][] kids = new int[2][p1.length];
		int[] rand = getRandomPair(p1.length);

		Set<Integer> tmp1 = new TreeSet<Integer>();
		Set<Integer> tmp2 = new TreeSet<Integer>();
		for (int i=rand[0]; i<=rand[1]; i++){
			kids[0][i] = p1[i];
			tmp1.add(p1[i]);
			kids[1][i] = p2[i];
			tmp2.add(p2[i]);
		}

		for (int i=rand[0]; i<=rand[1]; i++){
			if (!tmp1.contains(p2[i])){
				//element p2[i] wasnt copied
				int newplace = i;
				while (tmp1.contains(kids[0][newplace])){
					newplace = indexOf(p2, p1[newplace]);
				}
				kids[0][newplace] = p2[i];
				tmp1.add(p2[i]);
			}

			if (!tmp2.contains(p1[i])){
				//element p1[i] wasnt copied
				int newplace = i;
				while (tmp2.contains(kids[1][newplace])){
					newplace = indexOf(p1, p2[newplace]);
				}
				kids[1][newplace] = p1[i];
				tmp2.add(p1[i]);
			}
		}

		for (int i=0; i<p1.length; i++){
			if (!tmp1.contains(p2[i])){
				kids[0][i] = p2[i];
			}
			if (!tmp2.contains(p1[i])){
				kids[1][i] = p1[i];
			}
		}
		return kids;
	}

	protected int[][] cycleCrossover(int[] p1, int[] p2){
		int[][] kids = new int[2][p1.length];

		Set<Integer> tmp = new TreeSet<Integer>();
		int kid = 0;	//variable to know which parent copies to which child

		for (int i=0; i<p1.length; i++){
			if (!tmp.contains(p1[i])){
				int newplace = i;
				while (!tmp.contains(p1[newplace])){
					kids[kid][newplace] = p1[newplace];
					kids[1-kid][newplace] = p2[newplace];
					tmp.add(p1[newplace]);
					newplace = indexOf(p1, p2[newplace]);
				}
				kid = 1-kid;
			}
		}

		return kids;
	}

	//mutation
	protected int[] insertMutation(int[] org){
		int[] ans = new int[org.length];
		int[] rand = getRandomPair(org.length, 2);
		for (int i=0; i<=rand[0]; i++){
			ans[i] = org[i];
		}
		ans[rand[0]+1] = org[rand[1]];
		for (int i=rand[0]+2; i<=rand[1]; i++){
			ans[i] = org[i-1];
		}
		for (int i=rand[1]+1; i<org.length; i++){
			ans[i] = org[i];
		}
		return ans;
	}

	protected int[] swapMutation(int[] org){
		int[] ans = Arrays.copyOf(org, org.length);
		int[] rand = getRandomPair(org.length);
		ans[rand[0]] = org[rand[1]];
		ans[rand[1]] = org[rand[0]];
		return ans;
	}

	protected int[] inverseMutation(int[] org){
		int[] ans = Arrays.copyOf(org, org.length);
		int[] rand = getRandomPair(org.length);
		for (int i=rand[0] ; i<=rand[1]; i++){
			ans [i] = org[rand[1]+rand[0]-i];
		}
		return ans;
	}

	protected int[] scrambleMutation(int[] org){
		int[] ans = Arrays.copyOf(org, org.length);
		int[] rand = getRandomPair(org.length, 1);
		Vector<Integer> tmp = new Vector<Integer>();
		for (int i=rand[0]; i<=rand[1]; i++){
			tmp.add(org[i]);
		}
		Collections.shuffle(tmp);
		for (int i=rand[0] ; i<=rand[1]; i++){
			ans [i] = tmp.remove(0);
		}
		return ans;
	}

	//helping functions
	private int indexOf(int[] arr, int num){
		for (int i=0; i<arr.length; i++){
			if (arr[i] == num) return i;
		}
		return -1;
	}

	protected int[] getRandomPair(int size){
		return getRandomPair(size, 1, size);
	}

	protected int[] getRandomPair(int size, int minoffset){
		return getRandomPair(size, minoffset, size);
	}

	protected int[] getRandomPair(int size, int minoffset, int maxoffset){
		int rand1 = (int)(Math.random()*(double)(size-minoffset));
		int rand2 = (int)(Math.random()*(double)(Math.min(maxoffset, size-(rand1+minoffset)))) + rand1+minoffset;
		return new int[]{rand1, rand2};
	}




	// OLD bitstring operators
	protected boolean[] getRandomBitString(int size, double oneProbability){
		boolean[] ans = new boolean[size];
		for (int i=0; i<ans.length; i++){
			if (Math.random()>oneProbability){
				ans[i] = false;
			} else {
				ans[i] = true;
			}
		}
		return ans;
	}

	protected boolean[] bitwiseMutation(boolean[] bitString, double Pm){
		boolean[] ans = Arrays.copyOf(bitString, bitString.length);				//create a copy so we don't harm the original
		for (int i=0; i<ans.length; i++){
			double rand = Math.random();
			if (rand<Pm){
				ans[i] = !ans[i];
			}
		}
		return ans;
	}

	protected int[] bitwiseMutation(int[] bitString, double Pm, int range){
		int[] ans = Arrays.copyOf(bitString, bitString.length);				//create a copy so we don't harm the original
		for (int i=0; i<ans.length; i++){
			double rand = Math.random();
			if (rand<Pm){
				Random rand1 = new Random();
				ans[i] = rand1.nextInt(range);
			}
		}
		return ans;
	}

	protected boolean[][] singlePointCrossOver(boolean[] g1rep, boolean[] g2rep){
		int crossoverPoint = (int)(Math.random()*(g1rep.length-1)+1);
		boolean[] os1rep = new boolean[g1rep.length];
		boolean[] os2rep = new boolean[g2rep.length];
		for (int i=0; i<g1rep.length ; i++){
			os1rep[i] =  (i<crossoverPoint ? g1rep[i] : g2rep[i]);
			os2rep[i] =  (i<crossoverPoint ? g2rep[i] : g1rep[i]);
		}
		return new boolean[][]{os1rep, os2rep};
	}



	protected List<Genotype> getMatingPoolRouletteWheel(List<Genotype> population, int populationSize){	//TODO rounding is needed to overcome double errors
		List<Genotype> matingPool = new LinkedList<Genotype>();

		double fitnessSum = 0;
		for (Genotype g: population){
			fitnessSum = fitnessSum + fitness(g);
		}
		for (int i=0; i<populationSize; i++){	//creating the mating pool
			double rand = Math.random()*fitnessSum;
			for (Genotype g: population){
				rand = rand - fitness(g);
				if (rand<=0){
					matingPool.add(g);
					break;
				}
			}
		}
		Collections.shuffle(matingPool);
		return matingPool;
	}

	protected List<Genotype> getMatingPoolTournamentSelection(List<Genotype> population, int populationSize, int tournamentSize, int numWinners, double p){	//TODO rounding is needed to overcome double errors
		List<Genotype> matingPool = new LinkedList<Genotype>();

		while (matingPool.size()<populationSize){
			Vector<Genotype> tournament = new Vector<Genotype>();
			for (int i=0; i<tournamentSize; i++){
				int index = (int)(Math.random()*(double)populationSize);
				tournament.add(population.get(index));
			}

			for (int i=0; i<numWinners; i++){
				for (int j=0; j<tournament.size(); j++){
					if (Math.random()<p || j == tournament.size()-1){
						matingPool.add(tournament.remove(j));
						break;
					}
				}
			}
		}
		Collections.shuffle(matingPool);
		return matingPool;
	}

	public List<Genotype> getMatingPoolRandom(int size){
		List<Genotype> ans = new LinkedList<Genotype>();
		for (int i=0; i<size; i++){
			ans.add(createRandomInstance());
		}
		return ans;
	}
	public List<Genotype> elitist(List<Genotype> population,
			int populationSize, int elitism) {
		List<Genotype> ans = new LinkedList<Genotype>();

		double[][] tmp = new double[populationSize][2];
		for(int i=0; i<populationSize; i++){
			tmp[i][0]=i;
			tmp[i][1]=fitness(population.get(i));
		}
		mergeSort(tmp);
		for(int i=0; i<elitism; i++){
			Genotype g = population.get((int)tmp[tmp.length-(1+i)][0]).clone();
			ans.add(g);
		}
		return ans;
	}

	/**
	 * Mergesort algorithm.
	 * @param a an array of Comparable items.
	 */
	public static void mergeSort( double [][] a ) {
		double [][] tmpArray = new double[ a.length ][2];
		mergeSort( a, tmpArray, 0, a.length - 1 );
	}

	/**
	 * Internal method that makes recursive calls.
	 * @param a an array of Comparable items.
	 * @param tmpArray an array to place the merged result.
	 * @param left the left-most index of the subarray.
	 * @param right the right-most index of the subarray.
	 */
	private static void mergeSort( double [][] a, double [][] tmpArray,
			int left, int right ) {
		if( left < right ) {
			int center = ( left + right ) / 2;
			mergeSort( a, tmpArray, left, center );
			mergeSort( a, tmpArray, center + 1, right );
			merge( a, tmpArray, left, center + 1, right );
		}
	}

	/**
	 * Internal method that merges two sorted halves of a subarray.
	 * @param a an array of Comparable items.
	 * @param tmpArray an array to place the merged result.
	 * @param leftPos the left-most index of the subarray.
	 * @param rightPos the index of the start of the second half.
	 * @param rightEnd the right-most index of the subarray.
	 */
	private static void merge( double [][] a, double [][] tmpArray,
			int leftPos, int rightPos, int rightEnd ) {
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;

		// Main loop
		while( leftPos <= leftEnd && rightPos <= rightEnd )
			if( a[leftPos][1]< a[rightPos][1] ){
				tmpArray[tmpPos][0] = a[leftPos][0];
				tmpArray[tmpPos][1] = a[leftPos][1];
				tmpPos++;
				leftPos++;
			}
			else{
				tmpArray[tmpPos][0] = a[rightPos][0];
				tmpArray[tmpPos][1] = a[rightPos][1];
				tmpPos++;
				rightPos++;
			}
		while( leftPos <= leftEnd ){    // Copy rest of first half
			tmpArray[ tmpPos ][0] = a[ leftPos ][0];
			tmpArray[ tmpPos ][1] = a[ leftPos ][1];
			tmpPos++;
			leftPos++;
		}
		while( rightPos <= rightEnd ){  // Copy rest of right half
			tmpArray[ tmpPos ][0] = a[ rightPos ][0];
			tmpArray[ tmpPos ][1] = a[ rightPos ][1];
			tmpPos++;
			rightPos++;
		}
		// Copy tmpArray back
		for( int i = 0; i < numElements; i++, rightEnd-- ){
			a[ rightEnd ][0] = tmpArray[ rightEnd ][0];
			a[ rightEnd ][1] = tmpArray[ rightEnd ][1];
		}
	}


	//	public static void main(String[] args){
	//		int[] arr = test.getRandomIntString(9,1);
	//		int[] arr2 = test.getRandomIntString(9,1);
	//		System.out.println("p1 = " + Arrays.toString(arr));
	//		System.out.println("p2 = " + Arrays.toString(arr2));
	//		System.out.println();
	//		int[][] kids = test.cycleCrossover(arr, arr2);
	//		System.out.println(Arrays.toString(kids[0]));
	//		System.out.println(Arrays.toString(kids[1]));
	//	}

}
